package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no23;

import com.tucc.hello.leetcode.common.ListNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode[] lists = {
                ListNode.of(4, 5),
                ListNode.of(1, 2),
                ListNode.of(3, 6),
                ListNode.of(9, 11),
                ListNode.of(7)
        };
        ListNode head = solution.mergeKLists(lists);
        ListNode.print(head);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val)
        );
        Arrays.stream(lists).filter(Objects::nonNull).forEach(node ->{
            queue.add(node);
        });

        ListNode head = null;
        ListNode tail = null;
        while (!queue.isEmpty()) {
            if (queue.size() == 1) {
                if(tail == null){
                    head = queue.poll();
                }
                else{
                    tail.next = queue.poll();
                }
                break;
            }
            ListNode minNode = queue.poll();
            if(head == null){
                head = minNode;
                tail = head;
            }
            else{
                tail.next = minNode;
                tail = tail.next;
            }
            if(minNode.next != null){
                queue.offer(minNode.next);
            }
        }
        return head;
    }

}

